package algorithm;

/**
 * 大数相乘
 * <p>
 * 1234567891011121314151617181920 * 2019181716151413121110987654321 = [02492816912877266687794240983772975935013386905490061131076320]
 * <p>
 * https://blog.csdn.net/applehth/article/details/69659837
 * http://t.csdn.cn/pxY37
 * https://www.cnblogs.com/starrybird/p/4445566.html
 */
public class BigNumberMultiply {

    /**
     * Karatsuba乘法
     * 分治算法
     * 现有两个大数，x，y。
     * <p>
     * 首先将x，y分别拆开成为两部分，可得x1，x0，y1，y0。他们的关系如下：
     * <p>
     * x = x1 * 10m + x0；
     * <p>
     * y = y1 * 10m + y0。其中m为正整数，m < n，且x0，y0 小于 10m。
     * <p>
     * 那么 xy = (x1 * 10m + x0)(y1 * 10m + y0)
     * <p>
     * =z2 * 102m + z1 * 10m + z0，其中：
     * <p>
     * z2 = x1 * y1；
     * <p>
     * z1 = x1 * y0 +x0 * y1；
     * <p>
     * z0 = x0 * y0。
     * <p>
     * 此步骤共需4次乘法，但是由Karatsuba改进以后仅需要3次乘法。因为：
     * <p>
     * z1 = x1 * y0+ x0* y1
     * <p>
     * z1 = (x1 + x0) *(y1 + y0) - x1 * y1 - x0 * y0，
     * <p>
     * 故z1 便可以由一次乘法及加减法得到。
     */
    public static long karatsuba(long num1, long num2) {
        //递归终止条件
        if (num1 < 10 || num2 < 10) return num1 * num2;

        // 计算拆分长度
        int size1 = String.valueOf(num1).length();
        int size2 = String.valueOf(num2).length();
        int halfN = Math.max(size1, size2) / 2;

        /* 拆分为a, b, c, d */
        long a = Long.valueOf(String.valueOf(num1).substring(0, size1 - halfN));
        long b = Long.valueOf(String.valueOf(num1).substring(size1 - halfN));
        long c = Long.valueOf(String.valueOf(num2).substring(0, size2 - halfN));
        long d = Long.valueOf(String.valueOf(num2).substring(size2 - halfN));

        // 计算z2, z0, z1, 此处的乘法使用递归
        long z2 = karatsuba(a, c);
        long z0 = karatsuba(b, d);
        long z1 = karatsuba((a + b), (c + d)) - z0 - z2;

        return (long) (z2 * Math.pow(10, (2 * halfN)) + z1 * Math.pow(10, halfN) + z0);
    }

    public static String karatsuba2(String num1, String num2) {
        //递归终止条件
        if (num1.length() + num2.length() < 15) {
            long l = Long.parseLong(num1) * Long.parseLong(num2);
            return l + "";
        }
        // 计算拆分长度
        int size1 = num1.length();
        int size2 = num2.length();
        int halfN = Math.max(size1, size2) / 2;

        /* 拆分为a, b, c, d */
        String a = num1.substring(0, size1 - halfN);
        String b = num1.substring(size1 - halfN);
        String c = num2.substring(0, size2 - halfN);
        String d = num2.substring(size2 - halfN);

        // 计算z2, z0, z1, 此处的乘法使用递归
        String z2 = karatsuba2(a, c);
        String z0 = karatsuba2(b, d);
        String z1 = reduce( karatsuba2(addString(a, b), addString(c, d)) ,( addString(z0 , z2)));
        StringBuilder sb1 = new StringBuilder(z2);
        for (int i = 0; i < 2 * halfN; i++) {
            sb1.append("0");
        }
        StringBuilder sb2 = new StringBuilder(z1);
        for (int i = 0; i <  halfN; i++) {
            sb2.append("0");
        }
        return addString(addString(sb1.toString(), sb2.toString()), z0);


    }

    public static String addString(String num1, String num2) {
        StringBuilder builder = new StringBuilder();
        int carry = 0;
        for (int i = num1.length() - 1, j = num2.length() - 1;
             i >= 0 || j >= 0 || carry != 0;
             i--, j--) {
            int x = i < 0 ? 0 : num1.charAt(i) - '0';
            int y = j < 0 ? 0 : num2.charAt(j) - '0';
            int sum = (x + y + carry) % 10;
            builder.append(sum);
            carry = (x + y + carry) / 10;
        }
        return builder.reverse().toString();
    }

    public static String reduce(String max, String min) {
        StringBuilder builder = new StringBuilder();
        int carry = 0;
        for (int i = max.length() - 1, j = min.length() - 1;
             i >= 0 || j >= 0 || carry != 0;
             i--, j--) {
            int x = i < 0 ? 0 : max.charAt(i) - '0';
            int y = j < 0 ? 0 : min.charAt(j) - '0';
            int red = x - carry - y;
            if (red < 0 ) {
                red = 10+red;
                carry = 1;
            }else{
                carry = 0;
            }
            builder.append(red);
        }
        return builder.reverse().toString();
    }


    /**
     * https://leetcode.cn/problems/multiply-strings/solutions/372098/zi-fu-chuan-xiang-cheng-by-leetcode-solution/
     * @param num1
     * @param num2
     * @return
     *
     * 竖式乘法
     */
    public static String multiply(String num1, String num2) {
        if("0".equals(num1) || "0".equals(num2)){
            return "0";
        }
        int len1=num1.length();
        int len2=num2.length();
        int[] ans=new int[len1+len2];
        for(int i=len1-1;i>=0;i--){
            int value1=num1.charAt(i)-'0';
            for(int j=len2-1;j>=0;j--){
                int value2=num2.charAt(j)-'0';
                int sum=ans[i+j+1]+value1*value2;
                ans[i+j+1]=sum%10;
                ans[i+j]+=sum/10;
            }
        }
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<ans.length;i++){
            if(i==0 && ans[i]==0){
                continue;
            }
            sb.append(ans[i]);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
//        String s = karatsuba2("2019181716151413121110987654321", "1234567891011121314151617181920");
//        String s = karatsuba2("201", "2341234567891");
        String s = multiply("201918171615141312111098765432110987654321", "1234567891011121314151617181920");
        System.out.println(s);

//        for (int i = 0; i < 50; i++) {
//            long x = (long) (Math.random() * 1000000);
//            long y = (long) (Math.random() * 1000000);
//            String reduce = karatsuba2(x + "", y + "");
//            long intR = x * y;
//            String format = String.format("x=%d, y=%d.方法：%s，数字：%d，布尔值：%b", x, y, reduce, intR, Long.valueOf(reduce).equals(intR));
//            System.out.println(format);
//        }

    }
}
